package blue.global.tree;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 抽象类，只实现 ITree<T>.add() 方法<br>
 * 至于 ITree<T>.traverse() 方法，则需要子类去实现
 * 
 * @param <T> 树的节点项类型，必须实现 ITreeNodeItem 接口
 * @author zhengj
 * @since 1.0
 */
public abstract class AbstractTree<T extends ITreeNodeItem> implements ITree<T>
{
	private TreeNode head;
	//private TreeNode curNode;

	public AbstractTree()
	{
		head = new TreeNode();
	}

	@Override
	public void add(T item)
	{
		if (item.getUpNo() == null || item.getUpNo().equals("")) // 添加根节点
		{
			if (head.child == null) // 如果不存根节点，就添加
			{
				TreeNode node = new TreeNode();
				node.item = item;
				head.child = node;
			}
		}
		else // 添加非根节点
		{
			this.add(head.child, item);
		}
	}

	/**
	 * 把一个非根节点添加到当前树中<br>
	 * 具有相同节点的 getNo() 不会添加到当前树中<br>
	 * 
	 * @param node 根节点
	 * @param item 非根节点项
	 */
	private void add(TreeNode node, T item)
	{
		if (node == null)
			return;
		
		if (node.item.getNo().equals(item.getUpNo()))
		{
			this.addItem(node, item);
		}
		else
		{
			this.add(node.child, item);
			this.add(node.next, item);
		}
		
	}

	/**
	 * 在当前节点的子节点的末尾添加一个节点
	 * 
	 * @param node 当前节点
	 * @param item 要添加的节点项
	 */
	private void addItem(TreeNode node, T item)
	{
		TreeNode n = new TreeNode();
		n.item = item;
		if (node.child == null)
		{
			node.child = n;
			//curNode = n;
		}
		else
		{
			node = node.child;
			while (node.next != null)
			{
				node = node.next;
			}
			node.next = n;
		}
		/*else
		{
			if (curNode.item.getNo() != item.getNo()) // 序号不一样才添加
			{
				curNode.next = n;
				curNode = n;
			}
		}*/
	}

	@Override
	public void add(List<T> itemList)
	{
		if (itemList == null || itemList.size() == 0) // 空节点项列表
			return;

		this.add(itemList.get(0)); // 添加根节点项
		for (int i = 1; i < itemList.size(); i++) // 迭代添加非根节点项
		{
			this.add(head.child, itemList.get(i));
		}
	}

	@Override
	public void orderAndAdd(List<T> itemList)
	{
		if (itemList == null || itemList.size() == 0) // 空节点项列表
			return;

		// 对 itemList 升序排序
		Collections.sort(itemList, new Comparator<ITreeNodeItem>()
		{
			@Override
			public int compare(ITreeNodeItem node, ITreeNodeItem other)
			{
				return node.getNo().compareTo(node.getNo());
			}
		});

		this.add(itemList);
	}

	/**
	 * 取得树的头节点<br>
	 * 头节点的子节点也就是 getHead().child 才是树的根节点
	 * 
	 * @return 树的头节点
	 */
	protected TreeNode getHead()
	{
		return head;
	}
	
	@Override
	public T getRoot()
	{
		if (head == null || head.child == null)
			return null;
		
		return head.child.item;
	}

	/**
	 * 树的节点
	 */
	protected class TreeNode
	{
		public T item;
		public TreeNode child;
		public TreeNode next;
	}
}
